Linked List

# Python 연결 리스트 구현 예제
class Node:
    """연결 리스트의 노드"""
    def __init__(self, data):
        self.data = data      # 데이터 저장
        self.next = None      # 다음 노드 포인터
        self.prev = None      # 이전 노드 포인터 (이중 연결 리스트용)


class LinkedList:
    """단일 연결 리스트 구현"""
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    def append(self, data):
        """맨 뒤에 노드 추가 - O(1)"""
        new_node = Node(data)
        if not self.head:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self._size += 1

    def prepend(self, data):
        """맨 앞에 노드 추가 - O(1)"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        if not self.tail:
            self.tail = new_node
        self._size += 1

    def delete(self, data):
        """값으로 노드 삭제 - O(n)"""
        if not self.head:
            return False

        # 헤드 삭제의 경우
        if self.head.data == data:
            self.head = self.head.next
            if not self.head:
                self.tail = None
            self._size -= 1
            return True

        # 중간/끝 노드 삭제
        current = self.head
        while current.next:
            if current.next.data == data:
                if current.next == self.tail:
                    self.tail = current
                current.next = current.next.next
                self._size -= 1
                return True
            current = current.next
        return False

    def find(self, data):
        """값으로 노드 검색 - O(n)"""
        current = self.head
        index = 0
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1

    def __len__(self):
        return self._size

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

    def __repr__(self):
        return " -> ".join(str(item) for item in self) + " -> None"


# 사용 예제
if __name__ == "__main__":
    ll = LinkedList()
    ll.append(1)
    ll.append(2)
    ll.append(3)
    ll.prepend(0)

    print(f"리스트: {ll}")           # 0 -> 1 -> 2 -> 3 -> None
    print(f"길이: {len(ll)}")         # 4
    print(f"2의 위치: {ll.find(2)}")  # 2

    ll.delete(2)
    print(f"삭제 후: {ll}")           # 0 -> 1 -> 3 -> None

// JavaScript 연결 리스트 구현 예제
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.prev = null;  // 이중 연결 리스트용
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this._size = 0;
    }

    // 맨 뒤에 노드 추가 - O(1)
    append(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this._size++;
        return this;
    }

    // 맨 앞에 노드 추가 - O(1)
    prepend(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
        if (!this.tail) {
            this.tail = newNode;
        }
        this._size++;
        return this;
    }

    // 값으로 노드 삭제 - O(n)
    delete(data) {
        if (!this.head) return false;

        // 헤드 삭제
        if (this.head.data === data) {
            this.head = this.head.next;
            if (!this.head) this.tail = null;
            this._size--;
            return true;
        }

        // 중간/끝 노드 삭제
        let current = this.head;
        while (current.next) {
            if (current.next.data === data) {
                if (current.next === this.tail) {
                    this.tail = current;
                }
                current.next = current.next.next;
                this._size--;
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 값으로 노드 검색 - O(n)
    find(data) {
        let current = this.head;
        let index = 0;
        while (current) {
            if (current.data === data) return index;
            current = current.next;
            index++;
        }
        return -1;
    }

    // 인덱스로 접근 - O(n)
    get(index) {
        if (index < 0 || index >= this._size) return null;
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    get size() {
        return this._size;
    }

    // 배열로 변환
    toArray() {
        const result = [];
        let current = this.head;
        while (current) {
            result.push(current.data);
            current = current.next;
        }
        return result;
    }

    toString() {
        return this.toArray().join(' -> ') + ' -> null';
    }

    // 이터레이터 지원
    *[Symbol.iterator]() {
        let current = this.head;
        while (current) {
            yield current.data;
            current = current.next;
        }
    }
}

// 사용 예제
const ll = new LinkedList();
ll.append(1).append(2).append(3).prepend(0);

console.log(`리스트: ${ll}`);           // 0 -> 1 -> 2 -> 3 -> null
console.log(`길이: ${ll.size}`);         // 4
console.log(`인덱스 2: ${ll.get(2)}`);   // 2
console.log(`2의 위치: ${ll.find(2)}`);  // 2

ll.delete(2);
console.log(`삭제 후: ${ll}`);           // 0 -> 1 -> 3 -> null

// for...of 사용 가능
for (const item of ll) {
    console.log(item);  // 0, 1, 3
}